package alg20241106;

public class Text2 {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        minWindow(s, t);

    }
    public static String minWindow(String ss, String tt) {
        //先把t中字符出现的次数存入哈希表
        int[] hash1 = new int[128];
        char[] t = tt.toCharArray();
        for(char ch : t){
            hash1[ch]++;
        }
        int[] hash2 = new int[128];
        char[] s = ss.toCharArray();
        int bigin = -1;
        int len = Integer.MAX_VALUE;
        for (int left = 0, right = 0,  count = 0; right < s.length; right++) {
            //进窗口   + 维护count
            int in = s[right];
            hash2[in]++;
            if(hash2[in] <= hash1[in]) count++;
            //判断
            while(count == tt.length()){
                //更新结果
                if(right - left + 1 < len){
                    bigin = left;
                    len = right - left + 1;
                }
                //维护count
                int out = s[left];
                if(hash2[out] <= hash1[out]) count--;
                //出窗口
                hash2[out]--;
                left++;
            }
        }
        if(bigin == -1) return "";
        return ss.substring(bigin, bigin + len);
    }
}
